package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName FindDisappearedNumbers
 * @Description FindDisappearedNumbers
 * @Author wanghaiwei
 * @Date 2023/1/17 15:13
 */
public class FindDisappearedNumbers {
    //原地哈希原理
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null) {
            return result;
        }
        for (int i = 0; i < nums.length; i++) {
            int colonyIndex = Math.abs(nums[i]) - 1;
            int aggressorValue = nums[colonyIndex];
            if (aggressorValue > 0) {
                nums[colonyIndex] = aggressorValue * -1;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                result.add(i+1);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        FindDisappearedNumbers solution = new FindDisappearedNumbers();
        String result = StringUtils.join(solution.findDisappearedNumbers(new int[]{4,3,2,7,8,2,3,1}),',');
        Assert.isTrue("5,6".equals(result) || "6,5".equals(result), "findDisappearedNumbers-4,3,2,7,8,2,3,1计算失败，预期：5,6，实际："+result);
        result = StringUtils.join(solution.findDisappearedNumbers(new int[]{1,1}),',');
        Assert.isTrue("2".equals(result), "findDisappearedNumbers-1,1计算失败，预期：2，实际："+result);
    }
}
